package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder3

/**
 * https://leetcode.cn/problems/balance-a-binary-search-tree/description
 * 题型： 二叉树的中序遍历+前序遍历，二分法
 * ```
 * 1382. 将二叉搜索树变平衡
 *
 * 你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。
 * 如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
 *
 * 示例 1：
 * 输入：root = [1,null,2,null,3,null,4,null,null]
 * 输出：[2,1,3,null,null,null,4]
 * 解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
 *
 * 示例 2：
 * 输入: root = [2,1,3]
 * 输出: [2,1,3]
 *
 *
 * 提示：
 *
 * 树节点的数目在 [1, 104] 范围内。
 * 1 <= Node.val <= 105
 * ```
 */
class leetcode_1382 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val root: TreeNode = n1
        n1.right = n2
        n2.right = n3
        n3.right = n4

        val actual = balanceBST(root)
        val expected = arrayListOf(2, 1, 3, null, null, null, 4)
        Assert.assertEquals(expected.toString(), printLevelOrder3(actual).toString())
    }

    fun balanceBST(root: TreeNode?): TreeNode? {
        /**
        题型： 二叉树的中序遍历+前序遍历，二分法

        思路：
        https://leetcode.cn/problems/balance-a-binary-search-tree/solutions/457827/1382-jiang-er-cha-sou-suo-shu-bian-ping-heng-gou-z
        使用中序遍历收集节点到List值中。
        然后，中序遍历中使用二分法构建树。

         */
        // 1 收集节点到List值中
        val list: ArrayList<TreeNode> = ArrayList()
        collect(root, list)

        // 2 把有序有组构建二叉搜索树
//        for (item in list) {
//            item.left = null
//            item.right = null
//        }
        return build(list, 0, list.size - 1)
    }

    fun collect(root: TreeNode?, list: ArrayList<TreeNode>) {
        // 1 确认函数的参数以及返回值
        // 2 确认终止条件
        if (null == root) {
            return
        }
        // 3 确认单层递归的处理逻辑：中序遍历
        // 左
        collect(root.left, list)

        // 中
        list.add(root)

        // 右
        collect(root.right, list)
    }

    fun build(list: ArrayList<TreeNode>, left: Int, right: Int): TreeNode? {
        // 1 确认函数的参数以及返回值
        // 2 确认终止条件
        if (left > right) {
            return null
        }
        // 3 确认单层递归的处理逻辑：前序遍历
        // 中
        // TODO: val mid = left + (right - left) / 2
        val mid = left + (right - left) / 2
        val root: TreeNode = list[mid]

        // 左
        root.left = build(list, left, mid - 1)

        // 右
        root.right = build(list, mid + 1, right)

        return root
    }
}